Program analysis is a discipline which underlies many of the most essential specialties of computer science. These include automatic parallelization, software testing, software verification, software debugging, compiler optimization and program transformation.
The purpose of program analysis is to determine whether a computer program satisfies a set of specified properties either at compile time (static analysis) or during controlled execution (dynamic analysis). Program analysis is an automated method for doing so based on program structure.
In the existing literature, the terms “information flow” and “information flow analysis” have been used to refer to several earlier forms of program analysis that attempt to combine control flow and data flow analysis in some manner other than that disclosed in this patent application. Unless otherwise noted, as used herein these terms refer to the unification of control flow and data flow analysis as disclosed herein.
Although the applications of information flow analysis are myriad, the focus of this section will be on one important application in which the need for new methods of program analysis has been characterized as “critical”: automatic parallelization. Copeland, M. V., “A chip too far?,” Fortune, September 2008, pp. 43-44.
Methods for Program Analysis have not Kept Pace with the Rapid Improvements in Computer Hardware
The computer industry is undergoing a major transition due to fundamental advances in chip design. In particular, the advent of multi-core processors is leading to a spectrum of new computing platforms from high performance computing on desktops to cloud computing. The common denominator in these trends is parallel processing. In parallel processing, a single program is divided into several pieces, and the pieces are executed simultaneously (“in parallel”) on multiple processors. An automatic parallelizer is a software tool which separates the program into the individual pieces.
Most existing methods of program analysis were developed in an era in which processing consisted of a single program being executed on a single processor. These methods were not developed with parallelization as a goal, and software tools based on these methods are not sufficient to fully exploit the performance of the new multi-processor machines.
The main exception is in the area of supercomputers, where some program analysis methods for parallelization, such as dependence analysis, have been developed. See Allen, R., Kennedy, K., “Optimizing Compilers for Modern Architectures,” Academic Press, 2002.
These methods tend to be restricted in their capabilities due to the problem domain, which is mathematical computations. In particular, these methods focus on mathematical operations involving arrays within loops, which are not as common in commercial applications. Even in this limited problem domain, these program analysis methods do not typically provide full automation, and must be supplemented by the skills of highly trained specialists and the use of niche languages to obtain satisfactory results.
Manual parallelization and the employment of niche languages do not constitute a realistic solution for commercial applications. As high performance computing migrates to the business world and even the home, there is an acute need for software tools which can automatically parallelize software written in mainstream languages such as Java. These must be based on a foundation of new methods of precise program analysis.